シャミアの秘密分散法:SSSS(Shamier's Secret Sharing Scheme)

n 人のユーザーを $ U_1, U_2, . . . , U_n とする

位数$ p は素数で，$ n < p

秘密 s は $ Z_p の要素

各 $ U_i には $ d_i ∈ Z_p が割り当てられる．なお，$ i ≠ j のとき $ d_i ≠ d_j

Ui の ID を di として利用

$ p と d_1, . . . , d_n はパラメータとして公開

ディーラー D ̸∈ {U1, U2, . . . , Un} の存在を仮定する

D は秘密情報 s から部分情報 (share) si を計算し，Ui に配る

①D は，各 $ 1 ≤ j ≤ t − 1 について，秘密かつ無作為に$ a_j ∈ Z_p を選び，

多項式 f(x) を以下のように定める

$ f(x) = s + a_1 x + a_2 x^2 + · · · + a_{t−1} x^{t−1} mod p

このとき，秘密 s について，s = f(0) である

https://scrapbox.io/files/619e4e778846fc0020a8b12c.png

②D は安全な通信路を介して $ s_i = f(d_i) を Ui に送る

n 人のパーティはそれぞれ値$ f(1), ..., f(n) mod\;p を受け取る。

③任意の t 人の利用者 $ U_{i1}, U_{i2}, . . . , U_{it} は以下のラグランジュ補間式で s を復元できる

$ s =∑^t_{{k=1}}s_{i_k}\prod_{1≤ℓ≤t,ℓ≠k} \frac{d_{i_ℓ}}{d_{i_ℓ} − d_{i_k}}mod p

これは、x 座標が相異なるn+1 点$ (x_1,y_1), (x_2,y_2),\cdots,(x_{n+1},y_{n+1}) を通る n 次以下の関数 y=P(x) が1つ定まるよという意味なので以下の式で表される

$ P(x)= ∑^{n+1}_{i=1}y_i\frac{f_i(x_i)}{f_i(x)}

ただし，$ f_i(x)=\displaystyle\prod_{k\neq i}(x-x_k)